Technical note: Find a hidden “treasure”

This paper deals with a two searchers game and it investigates the problem of how the possibility of finding a hidden object simultaneously by players influences their behavior. Namely, we consider the following two‐sided allocation non‐zero‐sum game on an integer interval [1,n]. Two teams (Player 1 and 2) want to find an immobile object (say, a treasure) hidden at one of n points. Each point i ∈ [1,n] is characterized by a detection parameter λ_i (μ_i) for Player 1 (Player 2) such that p_i(1 ? exp(?λ_ix_i)) (p_i(1 ? exp(?μ_iy_i))) is the probability that Player 1 (Player 2) discovers the hidden object with amount of search effort x_i (y_i) applied at point i where p_i ∈ (0,1) is the probability that the object is hidden at point i. Player 1 (Player 2) undertakes the search by allocating the total amount of effort X(Y). The payoff for Player 1 (Player 2) is 1 if he detects the object but his opponent does not. If both players detect the object they can share it proportionally and even can pay some share to an umpire who takes care that the players do not cheat each other, namely Player 1 gets q₁ and Player 2 gets q₂ where q₁ + q₂ ≤ 1. The Nash equilibrium of this game is found and numerical examples are given. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Constrained minimax optimization of continuous search efforts for the detection of a stationary target

Analytical resolution of search theory problems, as formalized by B.O. Koopman, may be applied with some model extension to various resource management issues. However, a fundamental prerequisite is the knowledge of the prior target density. Though this assumption has the definite advantage of simplicity, its drawback is clearly that target reactivity is not taken into account. As a preliminary step towards reactive target study stands the problem of resource planning under a min–max game context. This paper is related to Nakai's work about the game planning of resources for the detection of a stationary target. However, this initial problem is extended by adding new and more general constraints, allowing a more realistic modeling of the target and searcher behaviors. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

New heuristic methods for the capacitated multi‐facility Weber problem

In this paper we consider the capacitated multi‐facility Weber problem with the Euclidean, squared Euclidean, and ?_p‐distances. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the distance between them. We first present a mixed integer linear programming approximation of the problem. We then propose new heuristic solution methods based on this approximation. Computational results on benchmark instances indicate that the new methods are both accurate and efficient. © 2006 Wiley Periodicals, Inc. Naval Research Logistics 2006     

Probabilistic resource pooling games

We study a setting with a single type of resource and with several players, each associated with a single resource (of this type). Unavailability of these resources comes unexpectedly and with player‐specific costs. Players can cooperate by reallocating the available resources to the ones that need the resources most and let those who suffer the least absorb all the costs. We address the cost savings allocation problem with concepts of cooperative game theory. In particular, we formulate a probabilistic resource pooling game and study them on various properties. We show that these games are not necessarily convex, do have non‐empty cores, and are totally balanced. The latter two are shown via an interesting relationship with Böhm‐Bawerk horse market games. Next, we present an intuitive class of allocation rules for which the resulting allocations are core members and study an allocation rule within this class of allocation rules with an appealing fairness property. Finally, we show that our results can be applied to a spare parts pooling situation.     

基于遗传算法舰船装载码头配置方案优化

两栖输送舰船码头装载过程中,如何科学配置装载码头,使得整个装载任务完成时间最短是部队制定装载方案需要解决的重要难题。依据码头装载配置特点和要求,运用军事运筹学多目标规划理论构建装载码头配置规划模型,并运用遗传算法理论和计算机编程工具实现码头配置规划模型的优化解算。从而提高了部队两栖输送舰船码头装载方案制定的科学性和时效性。     

Budget allocation,national security,military intelligence,and human capital: a dynamic model

This study develops a dynamic model that integrates military intelligence into the defense capability of the country and the optimal allocation of its government budget. We assert that the effectiveness of the country’s military intelligence is contingent on the quality of its human capital, which, in turn, implies a long-term positive relationship between the government’s various civilian expenditures and its capacity to achieve a cost-effective intelligence and, hence, military capability. This relationship is developed within a multiple-period arms race model between two rivals. Using this model and stylized data for the Israeli–Syrian arms race, we show that an appropriate budget shift from defense to civilian expenditures during the initial periods of the planning horizon will gradually (over a decade, say) increase the quality of human capital in the country and, thus, the effectiveness of its intelligence, which, in turn, will increase the country’s future security and welfare.     

Attrition through a partially coordinated area defense

An area defense consists of several groups that act independently, i.e., do not communicate with each other. Each group has a fixed number of defenders and a controller that allocates these defenders optimally against the individual attackers comprising an attack. We analyze the effectiveness of this partially coordinated defense against a simultaneous attack of known size in which all attackers are considered to be equally lethal. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Short‐term capacity allocation problem with tool and setup constraints

We consider a short‐term capacity allocation problem with tool and setup constraints that arises in the context of operational planning in a semiconductor wafer fabrication facility. The problem is that of allocating the available capacity of parallel nonidentical machines to available work‐in‐process (WIP) inventory of operations. Each machine can process a subset of the operations and a tool setup is required on a machine to change processing from one operation to another. Both the number of tools available for an operation and the number of setups that can be performed on a machine during a specified time horizon are limited. We formulate this problem as a degree‐constrained network flow problem on a bipartite graph, show that the problem is NP‐hard, and propose constant factor approximation algorithms. We also develop constructive heuristics and a greedy randomized adaptive search procedure for the problem. Our computational experiments demonstrate that our solution procedures solve the problem efficiently, rendering the use of our algorithms in real environment feasible. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

基于非对称balls-into-bins的高效平衡负载分配模型

在大规模数据中心和P2P覆盖网络等复杂网络负载平衡分配中,前人提出了多种多样的负载分配方法,但许多方法为了达到更好的平衡负载指标,追求越来越复杂的算法,使得时间复杂度和算法复杂度很难控制在合理的范围之内。本文在研究了经典balls-into-bins、Azar balls-into-bins和balls into non-uniformbins等模型的基础上,提出了一种新颖高效的非对称balls-into-bins平衡负载分配模型,该模型具有异构的balls、异构的bins,以及不同的bin选择概率,能以很高的概率将最大负载均衡地控制在合理的范围内,通信负载很小,且具有很好的可扩展性,通过拓展,该模型在负载平衡的诸多领域都将有广阔的应用空间。     

基于巡逻历史与道路优先级的武警巡逻策略

针对武警巡逻车辆配置问题,引入了Dijkstra最短路径算法、K—means聚类算法以及计算几何的相关理论,建立了一套警车巡逻模型,并提出了评价巡逻效果的量化评价标准。采用Dijkstra与K—means算法解决了静态警车配置问题;针对警车动态巡逻方案的设计,提出了基于巡逻历史与道路优先级的道路概率选择算法,并给出了不同情况下的警车配置以及巡逻方案。通过MATLAB仿真实验,证明了算法及模型的先进性和实用性。